package l.l.w.CodingInterviews;

import java.util.Stack;

/**
 * Created by llw on 2018/3/24/0024.
 */
public class 二叉搜索树与双向链表 {

    public TreeNode Convert1(TreeNode p) {
        if(p == null) return p;
        TreeNode pre = new TreeNode(0);
        TreeNode save = pre;
        TreeNode head;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        head = p;
        while(!stack.isEmpty() || head != null){
            if(head != null){
                stack.push(head);
                head = head.left;
            }else{
                TreeNode root = stack.pop();
                pre.right = root;
                root.left = pre;
                pre = root;
                head = root.right;
            }
        }
        pre.right = null;
        save.right.left = null;
        return save.right;
    }
    public TreeNode Convert(TreeNode p) {
        if(p == null) return p;
        TreeNode result = new TreeNode(0);
        TreeNode pre = result;
        pre = inOrder(p,pre);
        pre.right = null;
        result.right.left = null;
        return result.right;
    }
    private TreeNode inOrder(TreeNode p, TreeNode pre){
        if(p == null) return pre;
        pre = inOrder(p.left,pre);
        pre.right = p;
        p.left = pre;
        pre = p;
        pre = inOrder(p.right,pre);
        return pre;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);

        TreeNode result = new 二叉搜索树与双向链表().Convert(root);
        System.out.println(result);
    }
}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }
}
